%arxiv
\subsection{Problem Statement and Our Results}\label{sec:results}

\subsubsection{Problem Statement}
In this paper, we consider the problem of finding a sparse cut in an undirected graph. Formally, given a graph $G = (V, E)$ with conductance $\phi$, we want to find a cut set whose conductance is close to $\phi$. Our goal is to design a distributed algorithm which finds a cut set with sparsity $\tilde O(\sqrt{\phi})$.   

\subsubsection{Our Results}
Our main contributions are two distributed algorithms in the CONGEST model to find sparse cuts with approximation guarantees.
Both our algorithms crucially use random walks.

\begin{theorem}(cf. Section \ref{sec:sparse-cut})
\label{thm:algo1}
Given an $n$-node network $G$ with a cut of balance $b$ and conductance at most $\phi$, there is a distributed algorithm {\sc SparseCut} (cf. Algorithm \ref{alg:sparsecut}) that outputs a cut of conductance at most $\tilde O(\sqrt{\phi})$ with high probability, in $\tilde O(\frac{1}{b}(\frac{1}{\phi} + n))$ rounds. In particular, to find a cut of constant balance, the {\sc SparseCut} algorithm takes $\tilde O(\frac{1}{\phi} + n)$ rounds and finds a cut (if it exists) with similar approximation.  
\end{theorem}

The second algorithm is a variant of the first algorithm and based on a PageRank-based approach. The second algorithm achieves the similar running time bound as above.\\ 

Using the above results, we also show:

\begin{theorem}\label{thm:cluster}
Given an $n$-node network $G$ and  source node $s$, there is a  distributed algorithm that  outputs a {\em local} cluster in $\tilde O(\frac{1}{\phi} + n)$ rounds, where $\phi$ is the conductance of the graph. 
\end{theorem}

To prove the above running time bound, we derive a technical result on computing  conductances of $n$ (different) cuts in linear time (cf. Lemma \ref{lem:parallel-conductance}).  

\noindent We note that the time bound of  $\tilde O(\frac{1}{\phi} + n)$  is linear in $n$ (the number of nodes) and $1/\phi$.  From the definition of conductance (cf. Definition \ref{def:conductance}), it is clear that for every graph,
$1/\phi = O(m)$ ($m$ is the number of edges) and for many graphs it can be much smaller, e.g., for expanders it is $O(1)$. Hence, the running time of our algorithms can be significantly faster than the naive bound of $O(m)$ (cf. Section \ref{sec:distmodel}), especially in well-connected dense graphs. We next show a lower bound on the time needed for any distributed algorithm to compute a (non-trivial) sparse cut.

\begin{theorem}(cf. Section \ref{sec:lower-bound})
\label{thm:lb}
There is a $n$-node graph in which any distributed approximation algorithm  for computing sparsest cut (within any non-trivial approximation ratio)  will take $\tilde \Omega(\sqrt{n} + D)$ rounds, where $D$ is the diameter of the graph.
\end{theorem}

Since $1/\phi = \Omega(D)$ for any graph, the above lower bound says that in general, one cannot hope to improve on the $1/\phi$ term
of our upper bound. 



\subsection{Outline of This Chapter}
The next two section developes the two different approach to compute sparse cuts. In Section \ref{sec:sparse-cut}, we present the standard random walk-based distributed algorithm for sparse cut problem, by introducing the main ideas. Section \ref{sec:local-cluster} describes on finding local cluster set. Then in Section \ref{sec:pagerank-algo}, we present the second algorithm using PageRank-based approach. Section \ref{sec:lower-bound} derive a general lower bound to the sparse cut computation problem. Finally, we conclude in Section \ref{sec:conclusion} by summarizing the results developed in this chapter and discuss some open problems. 








